#pragma once

#include <deque>
#include <vector>

namespace jianzhi_059
{

class Solution
{
public:
    std::vector<int> maxSlidingWindow(const std::vector<int>& nums, const int k)
    {
        if (nums.empty() || k == 0)
            return {};

        std::vector<int> max_win;
        std::deque<int> mono_queue;

        for (int i = 0; i < k; ++i) {
            auto num = nums.at(i);
            while (!mono_queue.empty() && num >= nums.at(mono_queue.back()))
                mono_queue.pop_back();
            mono_queue.push_back(i);
        }
        max_win.push_back(nums.at(mono_queue.front()));

        for (int i = k; i < (int)nums.size(); ++i) {
            if (mono_queue.front() == i - k)
                mono_queue.pop_front();

            auto num = nums.at(i);
            while (!mono_queue.empty() && num >= nums.at(mono_queue.back()))
                mono_queue.pop_back();
            mono_queue.push_back(i);

            max_win.push_back(nums.at(mono_queue.front()));
        }

        return max_win;
    }
};

class MaxQueue
{
public:
    int max_value()
    {
        if (m_queue.empty())
            return -1;
        return m_descending_queue.front();
    }

    void push_back(int value)
    {
        m_queue.push_back(value);
        while (!m_descending_queue.empty() && value > m_descending_queue.back())
            m_descending_queue.pop_back();
        m_descending_queue.push_back(value);
    }

    int pop_front()
    {
        if (m_queue.empty())
            return -1;
        auto front = m_queue.front();
        m_queue.pop_front();
        if (front == m_descending_queue.front())
            m_descending_queue.pop_front();
        return front;
    }
private:
    std::deque<int> m_queue;
    std::deque<int> m_descending_queue;
};

}  /* namespace jianzhi_059 */
